package com.cobla.struct.tree;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 二叉树<br/>
 * 孩子链式存储
 */
@Data
@NoArgsConstructor
@AllArgsConstructor
public class BiTree {
    private int data;
    private BiTree lChild, rChild;

    private void visit(){
        System.out.println("data = " + this.data);
    }

    private void visit(BiTree tree) {
        System.out.println("data = " + tree.data);
    }
    /**
     * 先序遍历
     */
    public void preOrderRecursion(){
        visit();
        this.lChild.preOrderRecursion();
        this.rChild.preOrderRecursion();
    }

    /**
     * 中序遍历
     */
    public void inOrderRecursion() {
        this.lChild.inOrderRecursion();
        visit();
        this.rChild.inOrderRecursion();
    }

    /**
     * 后序遍历
     */
    public void postOrderRecursion() {
        this.lChild.postOrderRecursion();
        this.rChild.postOrderRecursion();
        visit();
    }

    /**
     * 层次遍历
     */
    public void levelOrder() {
        LinkedBlockingQueue<BiTree> helper = new LinkedBlockingQueue();
        helper.add(this);
        while (!helper.isEmpty()) {
            BiTree parent = helper.poll();
            visit(parent);
            if (parent.getLChild() != null) {
                helper.add(parent.getLChild());
            }
            if (parent.getRChild() != null) {
                helper.add(parent.getRChild());
            }
        }
    }

    /**
     * 先序遍历，非递归
     */
    public void preOrderNonRecursion() {
        Stack<BiTree> treeStack = new Stack<BiTree>();
        treeStack.add(this);
        while (!treeStack.isEmpty()) {
            BiTree tree = treeStack.pop();
            visit(tree);
            if (tree.getRChild() != null) {
                treeStack.push(tree.getRChild());
            }
            if (tree.getLChild() != null) {
                treeStack.push(tree.getLChild());
            }
        }
    }

    /**
     * 中序遍历，非递归
     */
    public void inOrderNonRecursion() {
        Stack<BiTree> treeStack = new Stack<BiTree>();
        BiTree tree = this;

        while (!treeStack.isEmpty() || tree != null) {
            while (tree != null) {
                treeStack.push(tree);
                tree = tree.getLChild();
            }
            tree = treeStack.pop();
            visit(tree);
            tree = tree.getRChild();
        }
    }

    /**
     * 后序遍历，非递归
     */
    public void postOrderNonRecursion(){
        // 先右后左先序遍历
        Stack<BiTree> preStack = new Stack<BiTree>();
        // 逆后序遍历
        Stack<BiTree> reverseStack = new Stack<BiTree>();

        preStack.add(this);
        while (!preStack.isEmpty()) {
            BiTree tree = preStack.pop();
            reverseStack.push(tree);
            if (tree.getLChild() != null) {
                preStack.push(tree.getLChild());
            }
            if (tree.getRChild() != null) {
                preStack.push(tree.getRChild());
            }
        }

        while (!reverseStack.isEmpty()) {
            reverseStack.pop().visit();
        }
    }


}
